/*
 * @lc app=leetcode id=4 lang=cpp
 *
 * [4] Median of Two Sorted Arrays
 */
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();

        if (len1 < 1 && len2 < 1) {
            return 0;
        }

        int left  = (len1 + len2 + 1)/2;
        int right = (len1 + len2 + 2)/2;

        return (findKthNumber(nums1, 0, nums2, 0, left) + findKthNumber(nums1, 0, nums2, 0, right))/2;
    }

    double findKthNumber(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (i >= nums1.size()) 
            return nums2[j+k-1];
        if (j >= nums2.size()) 
            return nums1[i+k-1];

        if (k == 1) {
            return std::min(nums1[i], nums2[j]);
        }

        int midVal1 = (i+k/2-1 < nums1.size()) ? nums1[i+k/2-1] : INT_MAX;
        int midVal2 = (j+k/2-1 < nums2.size()) ? nums2[j+k/2-1] : INT_MAX;

        if (midVal1 < midVal2) {
            return findKthNumber(nums1, i+k/2, nums2, j, k-k/2);
        } else {
            return findKthNumber(nums1, i, nums2, j+k/2, k-k/2);
        }
    }
};

